Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts

摘要

Recent results of Kaplan et al., building on previous work by Kuwakado andMorii, have shown that a wide variety of classically-secure symmetric-keycryptosystems can be completely broken by quantum chosen-plaintext attacks(qCPA). In such an attack, the quantum adversary has the ability to query thecryptographic functionality in superposition. The vulnerable cryptosystemsinclude the Even-Mansour block cipher, the three-round Feistel network, theEncrypted-CBC-MAC, and many others. In this work, we study simple algebraicadaptations of such schemes that replace $(\mathbb Z/2)^n$ addition withoperations over alternate finite groups--such as $\mathbb Z/{2^n}$--and provideevidence that these adaptations are qCPA-secure. These adaptations furthermoreretain the classical security properties (and basic structural features)enjoyed by the original schemes. We establish security by treating the (quantum) hardness of the well-studiedHidden Shift problem as a basic cryptographic assumption. We observe that thisproblem has a number of attractive features in this cryptographic context,including random self-reducibility, hardness amplification, and--in many casesof interest--a reduction from the "search version" to the "decisional version."We then establish, under this assumption, the qCPA-security of several suchHidden Shift adaptations of symmetric-key constructions. We show that a HiddenShift version of the Even-Mansour block cipher yields a quantum-securepseudorandom function, and that a Hidden Shift version of the Encrypted CBC-MACyields a collision-resistant hash function. Finally, we observe that suchadaptations frustrate the direct Simon's algorithm-based attacks in moregeneral circumstances, e.g., Feistel networks and slide attacks.